package 中等.动态规划.子序列;

/**
 * 给定一个未排序的整数数组 nums ， 返回最长递增子序列的个数 。
 * 注意 这个数列必须是 严格 递增的。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/number-of-longest-increasing-subsequence/
 */
public class 最长递增子序列的个数_673 {

    public static void main(String[] args) {

        System.out.println(findNumberOfLIS(new int[]{1, 2, 4, 3, 5, 4, 7, 2}));

    }

    /**
     * dp[i] 表示以 nums[i] 结尾的最长子序列长度是多少
     * cnt[i] 表示以 nums[i] 结尾的最长子序列数量是多少
     */
    public static int findNumberOfLIS(int[] nums) {
        int maxLen = 1, ans = 0;
        int[] dp = new int[nums.length];
        int[] cnt = new int[nums.length];

        for (int i = 0; i < dp.length; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }

        for (int i = 0; i < cnt.length; i++) {
            // 局部变量，以nums[i]结尾的最大长度
            int curLen = 1;
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    if (dp[j] + 1 > curLen) {
                        cnt[i] = cnt[j];
                        curLen = dp[j] + 1;
                    } else if (dp[j] + 1 == curLen) {
                        cnt[i] += cnt[j];
                    }
                }
            }

            if (cnt[i] == 0) cnt[i] = 1;
            if (curLen > maxLen) {
                ans = cnt[i];
                maxLen = curLen;
            } else if (curLen == maxLen) {
                ans += cnt[i];
            }
        }
        return ans;
    }

}
